// 设计一个算法，来实现二叉树的序列化与反序列化
// 序列化：将二叉树转为字符串数据表示
// 反序列化：将字符串数据转为二叉树结构

// 思路：前序遍历
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，递归栈的大小
function serialize(root) {
    if (!root) {
        return ''
    }
    return root.val + ',' + serialize(root.left) + ',' + serialize(root.right)
}

function TreeNode(val) {
    this.val = val
    this.left = null
    this.right = null
}

// 思路：后序遍历
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，递归栈的大小
function deserialize(str) {
    function dfs(arr) {
        if (!arr.length) {
            return null
        }
        let rootVal = arr.shift()
        if (!rootVal) {
            return null
        }
        // 这里需转为number
        let rootNode = new TreeNode(Number(rootVal))
        rootNode.left = dfs(arr)
        rootNode.right = dfs(arr)
        return rootNode
    }
    return dfs(str.split(','))
}

const root = {
    val: "A",
    left: {
        val: "B",
        left: {
            val: "D",
        },
        right: {
            val: "E",
        },
    },
    right: {
        val: "C",
        right: {
            val: "F",
        },
    },
};

console.log(serialize(root))
console.log(deserialize(serialize(root)))